1043. 分隔数组以得到最大和【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划

1. 📝 题目描述

• leetcode

给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。

返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。

---

示例 1：

输入：arr = [1,15,7,9,2,5,10], k = 3
输出：84
解释：数组变为 [15,15,15,9,10,10,10]

示例 2：

输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
输出：83

示例 3：

输入：arr = [1], k = 1
输出：1

---

提示：

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 10^9
• 1 <= k <= arr.length

2. 🎯 s.1 - 动态规划

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var maxSumAfterPartitioning = function (arr, k) {
  const n = arr.length
  const dp = new Array(n + 1).fill(0)
  for (let i = 1; i <= n; i++) {
    let maxVal = 0
    for (let j = 1; j <= Math.min(i, k); j++) {
      maxVal = Math.max(maxVal, arr[i - j])
      dp[i] = Math.max(dp[i], dp[i - j] + maxVal * j)
    }
  }
  return dp[n]
}

• 时间复杂度：$O(n\cdot k)$，其中 $n$ 是数组长度
• 空间复杂度：$O(n)$，DP 数组

算法思路：

• dp[i] 表示前 i 个元素分割后的最大和
• 对于每个位置 i，枚举最后一个子数组的长度 j（从 1 到 k）
• 维护子数组中的最大值 maxVal，更新 dp[i] = max(dp[i-j] + maxVal * j)